1. Field of Invention
The present invention relates to a method and apparatus for adaptive allocation of fair bandwidth in the links attached to routers of a backbone network comprising edge routers, core routers and links serving a plurality of flows from a plurality of Quality of Service (QoS) classes, so as to meet the end-to-end QoS requirements of each flow, avoid network congestion and utilize the network resources optimally.
2. Description of Prior Art
A backbone (communication) network comprises a plurality of edge and core routers interconnected by a plurality of links facilitating data communication between end user applications running in user computer devices at the user premises. The user devices, which comprise the end sources and the end destinations of the data traversing the backbone network, are connected to the edge routers by access links. The edge routers, which are connected to the user devices on one end, are also connected to core routers by core links on the other end. The core routers, however, are connected by core links only to other routers (either core or edge routers). Some enterprise backbone networks, e.g., Intranets, and public backbone networks, e.g., the Internet, comprise multiple network domains, where each network domain could utilize a different switching and routing protocol such as Internet Protocol (briefly IP), Frame Relay (briefly FR), Asynchronous Transfer Mode (briefly ATM), Multi-Protocol Label Switching (briefly MPLS) and Generalized Multi-Protocol Label Switching (briefly GMPLS). Since almost all user end applications communicate by IP, almost all edge routers support IP routing and switching.
Most user applications utilize Transport Control Protocol (briefly TCP) and User Datagram Protocol (briefly UDP) communication sockets, both generating IP packets. IP packets could be further encapsulated into network transmission units (briefly NTU) being transported through particular transport networks such as FR, ATM, MPLS and GMPLS. Efficient operation of a network requires tight control of the data flowing throughout the network. A data flow (briefly a flow) comprises all IP packets with the same QoS class flowing from a common source node, alternatively network number, to another common destination node, alternatively network number, along the same route. In accordance with IETF RFC 791, both, the source and the destination IP addresses, which also contain the respective network numbers, as well as the QoS class, are specified in the IP packet header. The QoS class is marked in the TOS header specifying performance requirements, e.g., minimum transmission rate, end-to-end packet delay and packet loss rate.
Flow control is the method of allocating the bandwidth of the network links between the flows and shaping the flow transmission rates accordingly. Flow control in a network is implemented by one or more distributed asynchronous and adaptive algorithms that are designed to meet some performance measures and to avoid network congestion. It is further desired from a flow control method to fully utilize the link bandwidths and to share the bandwidths between the flows in a fair manner as specified in reference [J. MO AND J. WALRAND, 2000]. Generally, fairness is subjective and several definitions exist. Therefore, it is of utmost importance to have a flow control method that can handle a wide range of fairness definitions. Although prior art provide a plurality of flow control methods, none of which handle multiple QoS classes in a manner that guarantee end-to-end QoS requirements for all flows, neither can they achieve fair bandwidth allocation between all flows and all QoS classes. The method of the present invention handles multiple QoS classes, guarantees end-to-end QoS requirement for every flow in any QoS class as well as allocates rates fairly in accordance to any given fairness definition within a wide range fairness notions.
Network flow controls could be practiced in several protocol layers such as the OSI network layer (e.g., IP layer), the OSI transport layer (e.g., TCP, ATM, MPLS and GMPLS). Also, the control processes could be executed in network processor devices (routers and switches) and/or in end user computer devices. A significant design consideration for flow control is to select the OSI layer. Prior art fair flow controls that are executed in network processor devices and handle a plurality of QoS classes, are applicable only in Virtual Circuit (VC) switched networks such as ATM (see U.S. Pat. Nos. 5,734,825; 5,966,381; 5,991,268; 6,185,187; 6,615,271; 6,324,165; 6,766,387; and 6,769,043). One embodiment of the method of the present invention that is executed in network processor devices controls the flows at the IP packet level rather than at the ATM cell level. It is also applicable to almost any transport network for the reasons explained herein. The generic format of the data traversing the network is dictated by the Application Program Interface (API) utilized in the user devices for networking applications. The two dominant APIs, which are not likely to change in the foreseeing future, are TCP and UDP sockets, both injecting IP data packets into the networks. Although IP packets could be encapsulated further into FR, ATM, MPLS or GMPLS NTUs, controlling the flows at the IP packet level is more general than controlling those at the NTU level since NTU format could change along the various network domains. Such a variety of domains would require a complex combination of flow control types, rather than a single generic one at the IP packet level. The latter is particular important for the Internet network and for multiple-domain enterprise networks.
Another significant design consideration is the scope of the flow control method. Some prior art fair flow controls that are executed in network processor devices and handle a plurality of QoS classes are limited to specific network topologies such as a metropolitan ring or a single switch (see U.S. Pat. Nos. 7,061,861 and 7,123,622). Some other prior art flow controls are limited to a single notion of fairness, known as max−min fairness (specified in reference [D. BERTSEKAS AND R. GALLAGER, 1992]), or a weighted variant of max−min fairness. The method of the present invention is applicable to any network topology and to a wide range of fairness notions including max−min fairness and proportional fairness as proposed in references [F. KELLY, A. MAULLOO AND D. TAN, 1998] and [J. MO AND J. WALRAND, 2000]. Hereinafter, the extended fairness notion is referred to as extended proportional fairness, or briefly fairness.
Whereas practical QoS requirements refer to end-to-end performance requirements, some prior art flow control guarantee only per-hop performance behavior (see reference [CISCO IOS, Release 12.0.] and the Differentiated Services QoS architecture, aka DiffServ [S. BLAKE, D. BLACK, M. CARLSON, E. DAVIES, Z. WANG AND W. WEISS, 1998]). Furthermore, each network processor router/switch requires manual configuration which should be coordinated across multiple network administrative domains and rely on a network provisioning tool. Another prior art method, the Integrated Services QoS architecture, aka IntServ, does guarantee end-to-end performance behavior but scarifies the scalability of the solution, hence applicable only for small networks. The method of the present invention is scalable, as DiffServ, and at the same time it also guarantees end-to-end performance, as IntServ. Furthermore, it adapts itself to the network traffic requiring only very simple configuration in the edge routers.
Some prior art network flow controls are executed in the end user devices rather than in the network processor devices. TCP flow control is the most common one and streaming application flow controls are others. Unlike the flow controls executed in ATM switches which adjust the transmission rates directly (known as rate-based flow control), prior art TCP flow controls are window-based methods which adjust the number of outstanding bytes that a flow can transmit, i.e., the window size. Prior art TCP window flow control are driven by the measurements of packet round trip times (briefly RTT); the resulting transmission rates and RTTs are implied and cannot be determined from the outset. Therefore, prior art TCP flow control suits only best-effort traffic flows. One embodiment of the method of the present invention also utilizes window-based flow control; however, it can also achieve pre-specified transmission rates and RTTs as required in the outset by the QoS classes. Prior art flow controls for streaming applications are rate-based and utilize the local network configuration of the user device to determine each rate target; these rates are not necessarily achievable.
In the quest for improving flow control, prior art research studies have studied the stability and the convergence of various flow control methods that can achieve fairness for a single flow QoS class known as the best effort class (see references [K. KAR, S. SARKAR AND L. TASSIULAS, 2002] [F. KELLY, A. MAULLOO AND D. TAN, 1998] [S. KUNNIYUR AND R. SRIKANT, 2003] [C. LAGOA, H. CHE AND B. A. MOVSICHOFF, 2004] [S. H. LOW AND D. E. LAPSLEY, 1999] [S. H. LOW, 2003] [L. MASSOULI AND J. ROBERTS, 2002] [J. MO AND J. WALRAND, 2000] [J. WANG D. X. WEI AND S. H. LOW, 2005]). These studies have inspired new fairness notions and have lead to better understanding of the stability issues involved in flow control. They have further contributed new rate-based and window-based flow controls that manifest fairness for best effort flows. Prior art rate-based fair flow controls are specified in references [K. KAR, S. SARKAR AND L. TASSIULAS, 2002] [F. KELLY, A. MAULLOO AND D. TAN, 1998] [S. KUNNIYUR AND R. SRIKANT, 2003] [C. LAGOA, H. CHE AND B. A. MOVSICHOFF, 2004] [S. H. LOW AND D. E. LAPSLEY, 1999] [L. MASSOULI AND J. ROBERTS, 2002] and U.S. Pat. Nos. 5,734,825; 5,966,381; 5,991,268; 6,185,187; 6,615,271; 6,324,165; 6,766,387; and 6,769,043. Prior art window-based fair flow controls are specified in references [J. MO AND J. WALRAND, 2000] D. WANG D. X. WEI AND S. H. LOW, and US patent applications 20050018617 and 20060050640. This prior art specifications are not addressing fair flow control for multiple flow QoS classes. Both embodiments of the method of the present invention, the window-based and the rate-based flow controls, do address extended proportional fairness for multiple flow QoS classes.
One shortcoming of prior art TCP flow control is that fairness, which is manifested in the case of single flow QoS class, breaks in the presence of non-conforming flows such as streaming application, e.g. RTSP, reference [H. SCHULZRINNE, A. RAO AND R. LANPHIER, and MMS (Microsoft media services]. Another shortcoming is that network congestion can emerge unless another protocol, known as congestion avoidance and implemented by an active queue management (AQM) module, is utilized (see references [D. CLARK AND W. FANG, 1998] [S. FLOYD AND V. JACOBSON, 1993] [V. MISRA, W. GONG AND D. TOWSLEY, 200] [Ref 19]). Currently, congestion avoidance is utilized by TCP but not by most of the streaming applications. Both shortcomings are addressed by the method of the present invention.
A common prior art rate-based traffic shaper, which is implemented in most current routers, is known as token bucket (see reference [A. K. PAREKH AND R. G. GALLAGER, 1993]). Token bucket is also utilized by one embodiment of the method of the present invention.